//given a sorted array that is rotated, 
//1. find if a element is exists (decision problem), 
//1.1 can it be implemented iteratively?
//2. find the minimum element
//3. find the index of a element if exists, or return -1 otherwise
// 6 7 1 2 3 4 5
#include <iostream>
#include <iterator>
#include <algorithm>
#include <string>
#include <sstream>

//left = 0, right = n-1
bool rotated_find(int * a, int left, int right, int key) {
	//terminate case
	if (left > right)
		return false;
	int mid = (left+right)/2;
	if (key == a[mid])
		return true;
	else if (key < a[mid]) {
		bool left_find = rotated_find(a,left, mid-1, key);
		bool right_find = false;
		if (a[mid] > a[right]) //right subarray is rotated, key can also be in right part
			right_find = rotated_find(a, mid+1, right, key);
		return left_find || right_find;
	}
	else { // key > a[mid]
		bool left_find = false;
		bool right_find = rotated_find(a, mid+1, right, key);
		if (a[left] > a[mid])
			left_find = rotated_find(a, left, mid-1, key);
		return left_find || right_find;
	}
}

int rotate_minimum(int a[], int left, int right){
	while (left+1 != right) {
		int mid = (left+right)/2;
		if (a[left] > a[mid])
			right = mid;
		else if (a[mid] > a[right])
			left = mid;
		else
			return a[left];
	}
	return std::min(a[left], a[right]); //when left==right or left+1==right
}

//left = 0, right = n-1
int rotated_find_index(int * a, int left, int right, int key) {
	//terminate case
	if (left > right)
		return -1;
	int mid = (left+right)/2;
	if (key == a[mid])
		return mid;
	else if (key < a[mid]) {
		int find = -1;
		if ( a[left] <= key )
			find = rotated_find_index(a,left, mid-1, key);
		if (find < 0 && a[mid] >= a[right]) //right subarray is rotated, key can also be in right part
			find = rotated_find_index(a, mid+1, right, key);
		return find;
	}
	else { // key > a[mid]
		int find = -1;
		if (key <= a[right])
			find = rotated_find_index(a, mid+1, right, key);
		if (find < 0 && a[left] >= a[mid])
			find = rotated_find_index(a, left, mid-1, key);
		return find;
	}
}

void test_rotate_find() {
	int a[] = {6, 8, 10, 0, 2, 4};
	int key;
	std::copy(a, a+sizeof(a)/sizeof(int), std::ostream_iterator<int>(std::cout, ", ")); std::cout << std::endl;
	while(std::cin >> key) {
		std::cout << (rotated_find(a, 0, sizeof(a)/sizeof(int)-1, key)? "found " : "not found ") << key << std::endl;
	}
}

void test_rotate_mininum() {
	std::string str;
	int a[100];
	std::cout << "enter the array\n";
	while(std::getline(std::cin, str) ){
		std::stringstream sstr(str);
		int n = 0;
		while(sstr >> a[n++]);
		std::cout << "minumin is " << rotate_minimum(a,0,n-2) << std::endl;
	}
}

void test_rotate_find_index() {
	//int a[] = {6, 8, 10, 0, 2, 4};
	int a[] = { 15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14};
	int key;
	std::copy(a, a+sizeof(a)/sizeof(int), std::ostream_iterator<int>(std::cout, ", ")); std::cout << std::endl;
	std::cout << "enter the key to find\n";
	while(std::cin >> key) {
		std::cout << rotated_find_index(a, 0, sizeof(a)/sizeof(int)-1, key) << std::endl;
	}
}